'''
https://leetcode.cn/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150
'''
from collections import deque
from typing import List


class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        def diff(s1, s2):
            return sum(c1 != c2 for c1, c2 in zip(s1, s2))

        visited = set(startGene)
        q = deque([startGene])
        step = 0
        while q:
            for _ in range(len(q)):
                u = q.popleft()
                if u == endGene:
                    return step
                for v in bank:
                    if v not in visited and diff(u, v) == 1:
                        q.append(v)
                        visited.add(v)
            step += 1
        return -1


s1 = 'AACCGGTT'
s2 = 'AACCGGTA'
bank = ["AACCGGTA"]
print(Solution().minMutation(s1, s2, bank))